class Solution:
    def permutation(self, s: str):
        c, res = list(s), []
        def dfs(x):
            if x == len(c) - 1:
                res.append(''.join(c)) # 添加排列方案
                print('rec', res)
                return
            dic = set()
            for i in range(x, len(c)):
                if c[i] in dic: continue # 重复，因此剪枝
                dic.add(c[i])
                print('dic', dic)
                print('cx:ci', c[x], c[i])
                c[i], c[x] = c[x], c[i] # 交换，将 c[i] 固定在第 x 位
                dfs(x + 1) # 开启固定第 x + 1 位字符
                c[i], c[x] = c[x], c[i] # 恢复交换
                print('huifu', 1)
        dfs(0)
        return res
s = 'adv'
r = Solution().permutation(s)
print(r)